//二叉查找(排序)树的实现 ———— Binary Search Tree
/*
  左子树的结点值 < 根结点值 < 右子树的结点值
*/

#include <cstdlib>

typedef struct BSTNode
{
    int data;                                            //数据域
    struct BSTNode *lchild = nullptr, *rchild = nullptr; //指针域
} BSTNode, *BSTree;

BSTNode *BST_Search(BSTree T, int key) //在BST中查找结点值为key的结点(非递归实现)【效率更高】
{
    while (T != nullptr && T->data != key) //若树空或结点值为key则退出循环
    {
        if (T->data > key) //若结点值大于key，则进入左子树查找
            T = T->lchild;
        else //若结点值小于key，则进入右子树查找
            T = T->rchild;
    }
    return T;
}

BSTNode *BSTSearch(BSTree T, int key) //在BST中查找结点值为key的结点(递归实现)
{
    if (T == nullptr) //查找失败
        return nullptr;
    if (T->data == key) //查找成功
        return T;
    else if (T->data > key) //若结点值大于key，则递归左子树
        return BSTSearch(T->lchild, key);
    else //若结点值小于key，则递归右子树
        return BSTSearch(T->rchild, key);
}

bool BST_Insert(BSTree &T, int key) //在BST中插入值为key的结点(非递归实现)
{
    while (1)
    {
        if (T == nullptr) //插入成功
        {
            T = (BSTree)malloc(sizeof(BSTNode));
            T->data = key;
            return true;
        }
        else
        {
            if (T->data == key) //插入失败(key值已存在)
                return false;
            else if (T->data > key) //若结点值大于key，则进入左子树查找
                T = T->lchild;
            else //若结点值小于key，则进入右子树查找
                T = T->rchild;
        }
    }
}

bool BSTInsert(BSTree &T, int key) //在BST中插入值为key的结点(递归实现)
{
    if (T == nullptr) //插入成功
    {
        T = (BSTree)malloc(sizeof(BSTNode));
        T->data = key;
        return true;
    }
    else if (T->data == key) //插入失败(key值已存在)
        return false;
    else if (T->data > key) //若结点值大于key，则递归左子树
        return BSTInsert(T->lchild, key);
    else //若结点值小于key，则递归右子树
        return BSTInsert(T->rchild, key);
}

void Creat_BST(BSTree &T, int str[], int n) //把数组str中的元素依次插入BST中
{
    T = nullptr; //初始时BST为空树
    int i = 0;
    while (i < n) //遍历数组str，依次插入至BST
    {
        BST_Insert(T, str[i]);
        i++;
    }
    return;
}